package com.day2_链表;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 题目：剑指 Offer 06. 从尾到头打印链表
 * 题目内容：输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
 * 示例 1：
 * 输入：head = [1,3,2]
 * 输出：[2,3,1]
 *
 * 思路：
 * 可以使用辅助栈法，遍历单链表将数据依次压入栈中，再依次出栈就好。
 * 用时：
 * 日期：20220816
 */

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}
//模拟单链表
class Solution {
    //定义头指针
    ListNode head;
    //定义尾指针
    ListNode last;

    public Solution() {
    }
    //    采用尾插法添加元素
    public void addInHead(int val){
        ListNode newNode=new ListNode(val);
        //判断头指针是否为空
        if(head==null){
            head=newNode;
        }
        //判断尾指针是否为空
        if(last==null){
            last=newNode;
        }
        else{
            //开始从尾部插入
            last.next=newNode;
            last=newNode;
        }
    }
    //遍历链表
    public void printLinkList(ListNode head){
        if(head==null){
            System.out.println("此链表为空");
        }
        else{
                ListNode temp=head;
                while(temp!=null){
                    System.out.print(temp.val);
                    temp=temp.next;
                }
        }
    }
    //剑指 Offer 06. 从尾到头打印链表
    public int[] reversePrint(ListNode head) {
        Deque<Integer> stack=new LinkedList<Integer>();
        ListNode temp=head;//头结点的位置不能移动
        while(temp!=null){
            stack.push(temp.val);
            temp=temp.next;
        }
        int[] vals=new int[stack.size()];
        //错误写法：for(int i=0;i<stack.size();i++){，这里不能用stack.size(),因为下面要弹栈，栈的长度会变。
        for(int i=0;i<vals.length;i++){
            vals[i]=stack.pop();
        }
        return vals;
    }
    //剑指 Offer 24. 反转链表
    public ListNode reverseList(ListNode head) {
        /*
        下面是错误写法
         */
//        ListNode p=head,q=head;//这两个指针用来遍历反转
//        ListNode temp;//记住p原来的位置
//        while(p.next!=null){
//            p=p.next;
//            temp=p;
//            p.next=q;//这个时候p原本的指向已经断掉了，后面再把temp赋给它也没用
//            p=temp;
//            q=temp;
//        }
        /*
        正确写法
        思路：遍历链表，用pre存放当前结点的前一个结点，用temp存放当前结点的后一个结点
         */
        ListNode pre=null,cur=head;//pre用于存放当前结点的前一个结点
        while(cur!=null){
            ListNode temp=cur.next;//记录当前结点的后一个结点
            cur.next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;//要返回pre,cur在上面循环结束时，已经知道最后一个结点的后一个结点了。
    }
}
public class 剑指Offer06_从尾到头打印链表 {
    public static void main(String[] args) {
        Solution s=new Solution();
        s.addInHead(1);
        s.addInHead(2);
        s.addInHead(3);
        s.printLinkList(s.head);
        System.out.println();
//        int[] result=s.reversePrint(s.head);
//        for (int re:result) {
//            System.out.print(re);
//        }
        s.head=s.reverseList(s.head);
        s.printLinkList(s.head);
    }
}
